import java.util.*;

public class GreedyAlgorithmPrimm extends PathAlg {
    private List<Node> nodes;
    private List<Node> notTaken;
    private Node tail;

	public void runAlgorithm() {
	    init();

  	    int pathCost = 0;   // increments in every iteration
        while(notTaken.size() > 0) {
            // Find closest and remove it from set 'notTaken'
            Node closest = null;
            for(Node n : notTaken) {
                if(closest == null || (n.cost/probabilities[n.id]) < (closest.cost/probabilities[closest.id]))
                    closest = n;
            }

            // Add EL cost and node in path
            closest.pathPosition = tail.pathPosition + 1;
            path[tail.pathPosition + 1] = closest.id;
            pathCost += costs[tail.id][closest.id];
            expectedLatency += pathCost * probabilities[closest.id];
            tail = closest; // keep track of tail node
            
            // Update notTaken set
            notTaken.remove(closest);   // remove just taken node
            for(Node n : notTaken) {    // update costs
                n.cost = pathCost + costs[tail.id][n.id];
            }
        }
	}

	private void init() {
        int nodeCount = costs.length;
	    notTaken = new ArrayList<Node>(nodeCount);
	    nodes = new ArrayList<Node>(nodeCount);
	    expectedLatency = 0;
	
		// Create nodes
		for(int i = 0; i < nodeCount; i++) {
		    Node n = new Node(i, costs[0][i]);
		    nodes.add(i,n);
		}

        // Initialize path and EL which we will greedily build up		
        tail = nodes.get(0);
        tail.pathPosition = 0;
        path[0] = 0;

		// Init notTaken list to contain all but start node
		for(int i = 1; i < nodeCount; i++) {
		    notTaken.add(nodes.get(i));
		}
	}
	
	public String getName() {
	    return "Primm";
    }
	
	// Class representing a node
	private class Node {
	    public int id, cost, pathPosition;
	    

	   	public Node(int id, int cost) {
    	    this.id = id;
    	    this.cost = cost;
    	    this.pathPosition = -1;
    	}
	}
}
